
// Definition for a binary tree node.
#include <iostream>
#include <vector>
using namespace std;

struct TreeNode
{
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
 public:
  /*
  vector<vector<int>> pathSum(TreeNode* root, int sum) {
    vector<vector<int>> res;
  }

  void dfs(TreeNode* root, int sum){
    // 出口
    if(root == NULL) return res;
    // 叶子节点
    if(root->right == NULL && root->left == NULL)
      if(sum == root->val)
  }
  private:*/

  vector<vector<int>> pathSum(TreeNode* root, int sum)
  {
    recur(root, sum);
    return res;
  }

  void recur(TreeNode* root, int tar)
  {
    // 递归出口
    if (root == NULL) return;
    path.push_back(root->val);
    tar -= root->val;
    if (tar == 0 && root->left == NULL && root->right == NULL) res.push_back(path);

    // 递推方程
    recur(root->left, tar);
    recur(root->right, tar);

    // 回溯：这里pop不止一次，因为在递推方程那里已经递归进去了，所以会pop多次，直到新的一条路径
    path.pop_back();
  }

 private:
  vector<vector<int>> res;
  vector<int> path;
};

int main()
{
  TreeNode* treeNode5 = new TreeNode(5);
  TreeNode* treeNode4 = new TreeNode(4);
  TreeNode* treeNode8 = new TreeNode(8);
  TreeNode* treeNode11 = new TreeNode(11);
  TreeNode* treeNode13 = new TreeNode(13);
  TreeNode* treeNode4_ = new TreeNode(4);
  TreeNode* treeNode7 = new TreeNode(7);
  TreeNode* treeNode2 = new TreeNode(2);
  TreeNode* treeNode5_ = new TreeNode(5);
  TreeNode* treeNode1 = new TreeNode(1);

  treeNode5->left = treeNode4;
  treeNode5->right = treeNode8;
  treeNode4->left = treeNode11;
  treeNode11->left = treeNode7;
  treeNode11->right = treeNode2;
  treeNode8->left = treeNode13;
  treeNode8->right = treeNode4_;
  treeNode4_->left = treeNode5_;
  treeNode4_->right = treeNode1;

  Solution solution;
  vector<vector<int>> res = solution.pathSum(treeNode5, 22);
  // System.out.println(res);

  return 0;
}
